#include "BTreeNode.h"

using namespace std;

/**
 * Class constructor for BTLeafNode, fills buffer with null bytes
 */
BTLeafNode::BTLeafNode()
{
	memset(buffer,'\0',PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	
	// zero out buffer before writing to it
	memset(buffer, '\0', PageFile::PAGE_SIZE);
	 
	return pf.read(pid,buffer);		// reads into the buffer
									// will return 0 if successful
									// will return error code from the read if error
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{	
	return pf.write(pid,buffer);	// writes from buffer into page file
									// will return 0 if successful
									// will return error code from teh write if error
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	char* p = buffer;
	if(p[0] == '\0')	// nothing in buffer
		return 0;
	else
	{
		int i = 0;
		while(p[0] != '\0' && p[sizeof(PageId)] != '\0')		// There is pageid pointer at end so check after the length of a pageid
		{
			i++;
			p += sizeof(RecordId) + sizeof(int);	// +8 for record Id
													// +4 for key value
		}
	
		return i;
	}	
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	int size = 0;
	char* p = buffer;
	char temp[PageFile::PAGE_SIZE];
	while(buffer[size] != '\0')		// to get the size of data in buffer already
		size++;
	
	if((size + sizeof(rid) + sizeof(key)) > PageFile::PAGE_SIZE)	// this means that there is not enough space in the page to add this
		return -1;		// -1 is error code for not enough room
	else
	{
		int eid;
		if(locate(key, eid) == -1)		// find where key should be placed, if -1 that means can't be found so place at end
		{
			int start = size - sizeof(PageId);		// Since PageId is at the end, have to insert it before the PageId
			memcpy(temp, (p + start), size - start);		// store values in temp array so can insert new record id and key
			memcpy((p+start), &rid, sizeof(RecordId));		// store record id
			memcpy((p+start+sizeof(RecordId)), &key, sizeof(int));	// store key
			memcpy((p+start+sizeof(RecordId))+sizeof(int), temp, size - start);		// restore data that was moved temporarily to insert new record id and key
		}
		else
		{
			int start = eid * (sizeof(RecordId) + sizeof(int));
			memcpy(temp, (p + start), size - start);		// store values in temp array so can insert new record id and key
			memcpy((p+start), &rid, sizeof(RecordId));		// store record id
			memcpy((p+start+sizeof(RecordId)), &key, sizeof(int));	// store key
			memcpy((p+start+sizeof(RecordId))+sizeof(int), temp, size - start);		// restore data that was moved temporarily to insert new record id and key
		}
		return 0;
	}
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
	
	int size = 0;
	char* p = buffer;
	char temp[((PageFile::PAGE_SIZE) + sizeof(RecordId) + sizeof(int))];	// in case the Node is full, have to be able to store another RecordId and Key
	if(sibling.buffer[0] != '\0')
		return -1;			// error since sibling node must start empty
	
	while(buffer[size] != '\0')		// to get the size of data in buffer already
		size++;
	
	if((size + sizeof(rid) + sizeof(key)) > PageFile::PAGE_SIZE)	// this means that there is not enough space in the page to add this
	{
		memcpy(temp, buffer, PageFile::PAGE_SIZE);		// copy the buffer to the larger temporary array
		int tempSize = 0;
		char* p1 = temp;
		char temp1[((PageFile::PAGE_SIZE) + sizeof(RecordId) + sizeof(int))];
		while(temp[tempSize] != '\0')		// to get the size of data in buffer already
			tempSize++;
		
		int eid;
		if(locate(key, eid) == -1)		// find where key should be placed, if -1 that means can't be found so place at end
		{
			int start1 = tempSize - sizeof(PageId);		// Since PageId is at the end, have to insert it before the PageId
			memcpy(temp1, (p1 + start1), tempSize - start1);		// store values in temp array so can insert new record id and key
			memcpy((p1+start1), &rid, sizeof(RecordId));		// store record id
			memcpy((p1+start1+sizeof(RecordId)), &key, sizeof(int));	// store key
			memcpy((p1+start1+sizeof(RecordId))+sizeof(int), temp1, tempSize - start1);		// restore data that was moved temporarily to insert new record id and key
		}
		else
		{
			int start1 = eid * (sizeof(RecordId) + sizeof(int));
			memcpy(temp1, (p + start1), tempSize - start1);		// store values in temp array so can insert new record id and key
			memcpy((p1+start1), &rid, sizeof(RecordId));		// store record id
			memcpy((p1+start1+sizeof(RecordId)), &key, sizeof(int));	// store key
			memcpy((p1+start1+sizeof(RecordId))+sizeof(int), temp1, tempSize - start1);		// restore data that was moved temporarily to insert new record id and key
		}
		
		int half = (getKeyCount()+1) / 2;		// This will return the eid of the halfway point
		tempSize += sizeof(rid) + sizeof(key);
		
		int start2;
		start2 = half *  (sizeof(int) + sizeof(RecordId));		// use the index to find starting spot
		memcpy(sibling.buffer, (p1 + start2), tempSize - start2);		// store values in sibling LeafNode
		while(start2 < PageFile::PAGE_SIZE)
		{
			p1[start2] = '\0';			// fill in the part copied in with Null terminated bytes
			start2 ++;
		}
		memcpy(buffer,temp,PageFile::PAGE_SIZE);

	}
	else
	{
		insert(key, rid);		// will add key and rid to appropriate spot
		int half = getKeyCount() / 2;		// This will return the eid of the halfway point
		size += sizeof(rid) + sizeof(key);
		
		int start;
		start = half *  (sizeof(int) + sizeof(RecordId));		// use the index to find starting spot
		memcpy(sibling.buffer, (p + start), size - start);		// store values in sibling LeafNode
		while(start < PageFile::PAGE_SIZE)
		{
			p[start] = '\0';			// fill in the part copied in with Null terminated bytes
			start ++;
		}
	}
	return 0;
	
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	int id = 0;
	int curKey;
	char* p = buffer;
	while(p[0] != '\0' && p[sizeof(PageId)] != '\0')		// There is pageid pointer at end so check after the length of a pageid
	{
		memcpy(&curKey,(p+sizeof(RecordId)),sizeof(int));	// This goes past the RecordId, into the key field, and copies the key into the curKey variable
		
		if(curKey >= searchKey)
		{
			eid = id;
			return 0;
		}
		
		id++;		// increase entry number
		p += sizeof(RecordId) + sizeof(int);	// +8 for record Id
												// +4 for key value
	}
	return -1;		// -1 return will be the error code for now
	
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
	char* p = buffer;
	if(eid < 0)
	{
		return -1;
	}
	
	while(p[0] != '\0' && p[sizeof(PageId)] != '\0')		// There is pageid pointer at end so check after the length of a pageid
	{
				
		if(eid == 0)
		{
			memcpy(&rid,p, sizeof(RecordId));			// Copies the RecordId from the buffer of the entry into the parameter
			memcpy(&key,(p+sizeof(RecordId)),sizeof(int));	// This goes past the RecordId, into the key field, and copies the key into the key parameter
			return 0;
		}
		eid--;		// decrease entry number
		p += sizeof(RecordId) + sizeof(int);	// +8 for record Id
												// +4 for key value
	}
	
	return -1;		// -1 return value as error code where entry not in buffer
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	PageId nextNode;		// PageId of next sibling node
	char* p = buffer;
	if(p[0] == '\0')	// nothing in buffer
	{
		return NULL;		// return NULL error since there is no nextNode because there needs to be at least 1 entry in this node
	}
	while(p[0] != '\0')	
	{
		
			
		p += sizeof(RecordId) + sizeof(int);	// +8 for record Id
												// +4 for key value
		if(p[sizeof(PageId)] != '\0')			// This goes to a value of PageId after an entry.  If there is an entry, then not at end of entries.
		{										// If there is not an entry, then there was the NextNodePtr
			memcpy(&nextNode, p, sizeof(PageId));
			return nextNode;
		}
		
	}
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
	char* p = buffer;
	if(p[0] == '\0')			// empty Node
		memcpy(p, &pid, sizeof(PageId));
			   
	while(p[0] != '\0')		// go until reach end of entries
	{
		if(p[sizeof(PageId)] == '\0')		// if 
		{
			memcpy(p, &pid, sizeof(PageId));
		}
		p += sizeof(RecordId) + sizeof(int);	// +8 for record Id
												// +4 for key value
	}
	
	return 0;
}




/**
 * Class constructor for BTNonLeafNode, fills buffer with null bytes
 */
BTNonLeafNode::BTNonLeafNode()
{
	memset(buffer,'\0',PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid,buffer);		// reads into the buffer
	// will return 0 if successful
	// will return error code from the read if error
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid,buffer);	// writes from buffer into page file
	// will return 0 if successful
	// will return error code from teh write if error
}


/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	char* p = buffer;
	if(p[0] == '\0')	// nothing in buffer
		return 0;
	else
	{
		int i = 0;
		while(p[0] != '\0' && p[sizeof(PageId)] != '\0')		// There is pageid pointer at end so check after the length of a pageid
		{
			i++;
			p += sizeof(PageId) + sizeof(int);	
		}
		
		return i;
	}	
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	int size = 0;
	int start = 0;
	int curKey;
	char* p = buffer;
	char temp[PageFile::PAGE_SIZE];
	
	while(buffer[size] != '\0')		// to get the size of data in buffer already
		size++;
	
	if(size < sizeof(PageId) + sizeof(int) + sizeof(PageId))
	{
		return -1;			// returns an error if not at least 2 Page Id's and a a key... it should be initialized with root already
	}
	
	else if(size + sizeof(PageId) + sizeof(int) > PageFile::PAGE_SIZE)
	{
		return -1;			// returns an error if no space ot insert in NonLeafNode
	}
		
	p += sizeof(PageId);
	
	while(p[0] != '\0')		// There is pageid pointer at end so check after the length of a pageid
	{
		memcpy(&curKey,p,sizeof(int));	// This goes past the RecordId, into the key field, and copies the key into the curKey variable
		if(key < curKey)
		{
			memcpy(temp, p, size - start);		// copy the Page id of the PageId before the higher valued key
			memcpy(p, &key, sizeof(int));	// copy key
			memcpy(p + sizeof(int), &pid, sizeof(PageId));		// copy page id
			memcpy(p + sizeof(int) + sizeof(PageId), temp, size - start);	// copy stuff in temp to end of buffer
			return 0;
		}
		
		start += sizeof(PageId) + sizeof(int);
		p += start;
	}
		// copies at end since the key is bigger than all the stored keys
	memcpy(p, &key, sizeof(int));				// copy key
	memcpy(p + sizeof(int), &pid, sizeof(PageId));		// copy page id
	return 0;
	
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	int size = 0;
	char* p = buffer;
	char temp[((PageFile::PAGE_SIZE) + sizeof(PageId) + sizeof(int))];	// in case the Node is full, have to be able to store another RecordId and Key
	if(sibling.buffer[0] != '\0')
		return -1;			// error since sibling node must start empty
	
	while(buffer[size] != '\0')		// to get the size of data in buffer already
		size++;
	
	if(size < sizeof(PageId) + sizeof(int) + sizeof(PageId))
	{
		return -1;			// returns an error if not at least 2 Page Id's and a a key... it should be initialized with root already
	}
	
	if((size + sizeof(pid) + sizeof(key)) > PageFile::PAGE_SIZE)	// this means that there is not enough space in the page to add this
	{
		memcpy(temp, buffer, PageFile::PAGE_SIZE);		// copy the buffer to the larger temporary array
		int tempSize = 0;
		char* p1 = temp;
		char temp1[((PageFile::PAGE_SIZE) + sizeof(PageId) + sizeof(int))];
		while(temp[tempSize] != '\0')		// to get the size of data in buffer already
			tempSize++;

		p1 += sizeof(PageId);
		int curKey;
		int start = 0;
		while(p1[0] != '\0')		// There is pageid pointer at end so check after the length of a pageid
		{
			memcpy(&curKey,p1,sizeof(int));	// This goes past the RecordId, into the key field, and copies the key into the curKey variable
			if(key < curKey)
			{
				memcpy(temp1, p1, tempSize - start);		// copy the Page id of the PageId before the higher valued key
				memcpy(p1, &key, sizeof(int));	// copy key
				memcpy(p1 + sizeof(int), &pid, sizeof(PageId));		// copy page id
				memcpy(p1 + sizeof(int) + sizeof(PageId), temp1, tempSize - start);	// copy stuff in temp to end of buffer
				return 0;
			}
			
			start += sizeof(PageId) + sizeof(int);
			p1 += start;
		}
		// copies at end since the key is bigger than all the stored keys
		memcpy(p1, &key, sizeof(int));				// copy key
		memcpy(p1 + sizeof(int), &pid, sizeof(PageId));		// copy page id

		// so now temp has the new buffer that needs to be split
		
		int half = (getKeyCount()+1) / 2;		// This will return the eid of the halfway point (+1 since we just added an entry)
		tempSize += sizeof(pid) + sizeof(key);
		
		int start2;
		start2 = half *  (sizeof(int) + sizeof(PageId));		// use the index to find starting spot
		memcpy(sibling.buffer, (p1 + start2), tempSize - start2);		// store values in sibling LeafNode
		memcpy(&midKey, (p1 + start2 - sizeof(int)), sizeof(int));		// store the middle key
		while((start2 < PageFile::PAGE_SIZE))
		{
			p1[start2 - sizeof(int)] = '\0';			// fill in the part copied in with Null terminated bytes, as well as the middle key value
			start2 ++;
		}
			  
		memcpy(buffer,temp,PageFile::PAGE_SIZE);
	}
	
	else
	{
		insert(key, pid);		// will add key and rid to appropriate spot
		int half = getKeyCount() / 2;		// This will return the eid of the halfway point
		size += sizeof(pid) + sizeof(key);
		
		int start;
		start = half *  (sizeof(int) + sizeof(PageId));		// use the index to find starting spot
		memcpy(sibling.buffer, (p + start), size - start);		// store values in sibling LeafNode
		memcpy(&midKey, (p + start - sizeof(int)), sizeof(int));		// store the middle key
		while(start < PageFile::PAGE_SIZE)
		{
			p[start - sizeof(int)] = '\0';			// fill in the part copied in with Null terminated bytes
			start ++;
		}
	}
	return 0;
	
}
		

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	int curKey;
	char* p = buffer;
	
	if(p[0] == '\0' || p[sizeof(PageId)] == '\0')
		return -1;										// this is an error because this means there is no key stored
	
	while(p[0] != '\0' && p[sizeof(PageId)] != '\0')		// There is pageid pointer at end so check after the length of a pageid
	{
		memcpy(&curKey,(p+sizeof(PageId)),sizeof(int));	// This goes past the RecordId, into the key field, and copies the key into the curKey variable
		
		if(searchKey < curKey)
		{
			memcpy(&pid, p, sizeof(PageId));		// copy the Page id of the PageId before the higher valued key
			return 0;
		}

		p += sizeof(PageId) + sizeof(int);	
	}
	memcpy(&pid, p, sizeof(PageId));		// means the search key is bigger than all the other keys so return the pageid at the end
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{

	char* p = buffer;
	
	memcpy(p, &pid1, sizeof(PageId));
	p += sizeof(PageId);
	memcpy(p, &key, sizeof(int));
	p += sizeof(int);
	memcpy(p, &pid2, sizeof(PageId));
	return 0;
}
